Many networks support secure group communication, wherein a group with multiple senders may transmit packets to a single receiver using a secure channel. Here, the transmitted packets are encrypted using a secret key shared between all the group members. As one example, distributed sensor networks (such as “Smart Grid” energy metering networks) rely on a multitude of sensors to report measurements, such as temperature, electricity consumption, etc, and this information may be communicated to a central node using a secure channel. One of the easiest types of attacks that an external adversary can launch, without any knowledge of the secret key, is a replay attack. A replay attack is a form of network attack in which an adversary captures packets from the network and then maliciously injects those packets into the network later so as to masquerade as a legitimate sender and attempt to have the receiver accept the replayed packets as fresh legitimate packets.
A standard solution to detect replay attacks is to use counters. These counters are internally stored at both the sender and the receiver, and incremented once per packet. The sender includes the counter in each packet and encrypts it along with the packet data. The receiver accepts a packet only if the counter on the decrypted packet is greater than the counter it has stored internally. However, notice that while a single secret key shared between all group members will suffice for encrypting the packets (or alternatively, the group members' key can be derived from the receiver's master secret), the receiver needs to maintain a separate counter for each sender. Further, notice that counters will only work if they are long enough (e.g., with 32 bits) so that they do not overflow and wrap-around after reaching a maximum value (e.g., 2^32-1 for a 32-bit counter) in a reasonably short duration. Thus, the use of counters does not scale well in a system with a large number of senders. As an example, if there are a million senders, maintaining a 32-bit counter per sender requires the receiver to store 32 million bits of state information. This can be a challenge for small devices.
More recent solutions use a combination of counters (at the sender) and a bloom filter (at the receiver). However, a bloom filter does not scale well when there are a large number of senders that transmit a large numbers of packets because the required state space depends on both the number of senders and the number of packets that are transmitted by each sender. As an example, if there are a million senders that transmit 1000 packets each, a bloom filter needs approximately 30 billion bits [(10^6)×(10^3)×log—2((10^6)×(10^3))] of state information.
Accordingly, there is a need for an improved replay attack detection solution that can be accomplished with substantially reduced state information relative to the prior art. Advantageously, the improved replay attack detection solution can be implemented in secure group communication networks with a large number of senders, with a state information storage overhead that is much less than the counter size per sender multiplied by the number of senders (e.g., 32 bits per sender×n senders) and that is independent of the number of packets transmitted by each sender. Embodiments of the present invention are directed to addressing this need.